package com.atwulidun.recursion;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 给定一个不含重复元素的数组，返回该数组可能的所有子集
public class SubSetI {
    private List<List<Integer>> list = new ArrayList<>();// 保存所有结果的list
    private List<Integer> temp = new ArrayList<>();// 保存每次结果并可以被重复利用的list
    private int[] num;// 外部传进来的不含重复元素的数组

    public SubSetI(int[] num) {
        this.num = num;
    }

    public void subSetI(int start, int end) {
        if (temp.size() == num.length) {
            list.add(new ArrayList<>(temp));// 特别要注意：这里不能list.add(temp)，因为temp指向的是同一块内存区域，虽然说添加的一瞬间temp里面的内容是你想要的内容
            // 但是由于回溯，最后temp里面会跟最开始一样都为null，因此list里面就会存一堆null
            return;
        }
        // 注意：将temp加入到list的语句要写在for循环的上面
        // 可以理解成将递归上一层的temp在这一层加进去
        // 也可以理解成先把空集加进去
        list.add(new ArrayList<>(temp));
        for (int i = start; i < end; i++) {
            temp.add(num[i]);
            subSetI(i + 1, end);// 注意：下一次的start == i + 1，而不是start + 1
            temp.remove(temp.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] num = {1, 2, 3};
        SubSetI subSetI = new SubSetI(num);
        subSetI.subSetI(0, num.length);
        System.out.println(subSetI.list);
    }
}
